package com.exercises;

import java.util.Enumeration;

class Exercise1049 {
    public static void main(String[] args) {

    }

    public static int lastStoneWeightII(int[] stones) {
        //最后一块石头的重量,可以理解为把石头分两堆,相减之后的重量
        //石头总和sum  假设一堆石头重量a 则另一堆位sum-a;
        //a-(sum-a)=0   a=sum/2的时候可以完全抵消
        //所以需要找到和最接近sum/2的一堆石头
        int sum = 0;
        int length = stones.length;
        for (int i = 0; i < length; i++) {
            sum += stones[i];
        }
        int target = sum / 2;
        //dp[i][j]=true 表示挑完到第i块石头 能凑出重量为j
        boolean[][] dp = new boolean[length + 1][target + 1];
        dp[0][0] = true;

        for (int i = 0; i < length; i++) {
            for (int j = 0; j <= target; j++) {
                if (j < stones[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
                }
            }
        }
        for (int j = target; j > 0; j--) {
            if (dp[length][j]) {
                return sum - 2 * j;
            }
        }
        return sum;
    }
}

